package leetcode.top100;


/**
 * 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。
 * <p>
 * 现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
 * <p>
 * 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums: [1, 1, 1, 1, 1], S: 3
 * <p>
 * 输出: 5
 * 解释:
 * <p>
 * -1+1+1+1+1 = 3
 * <p>
 * +1-1+1+1+1 = 3
 * <p>
 * +1+1-1+1+1 = 3
 * <p>
 * +1+1+1-1+1 = 3
 * <p>
 * +1+1+1+1-1 = 3
 * <p>
 * 一共有5种方法让最终目标和为3。
 * <p>
 * 注意:
 * <p>
 * 数组非空，且长度不会超过20。
 * <p>
 * 初始的数组的和不会超过1000。
 * <p>
 * 保证返回的最终结果能被32位整数存下。
 * <p>
 * <p>
 * 本质见{@link baseclass.j_dp.dp}
 * @since 2019/12/30 0030 下午 2:28
 */
public class Code494_TargetSumInArray_目标和2 {


    public static void main(String[] args) {
        int[] nums = {1000};
        System.out.println(findTargetSumWays(nums, -1000));
    }

    private static int res = 0;

    public static int findTargetSumWays(int[] nums, int S) {
        if (nums == null || nums.length == 0) return 0;
        if (S > MAX_SUM) return 0;
//        process1(nums, S, 0);
//        return res;
        return dp2(nums, S);
    }

    /**
     * 方式4的空间优化
     */
    private static int dp2(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) sum += num;
        if ((sum + S) / 2 == 1) return 0;
        int target = (sum + S) / 2;
        //寻找和为target的数量
        int[][] dp = new int[nums.length][target + 1];
        //第0位置可以组成 0或nums[0]
        dp[0][0] = 1;
        //注意要判断
        if(nums[0] <= target)
            //主要要在原来的基础上加，避免nums[0] = 0
            dp[0][nums[0]] += 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j <= target; j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i])
                    dp[i][j] += dp[i-1][j-nums[i]];

            }
        }
        return dp[nums.length-1][target];
    }
    /**
     * 方式4：设集合为Q，目标为S。
     * <p>
     * 最终S是由集合P取正和集合Q取负组成，即 S = P - Q
     * <p>
     * P + Q + P-Q = sum + S = 2P,
     * <p>
     * 从而化简成在集合Q中寻找是否能组成 P = (sum+S)/2的 0-1背包问题
     */
    private static int dp2_2(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) sum += num;
        if ((sum + S) / 2 == 1) return 0;
        int target = (sum + S) / 2;
        //寻找和为target的数量
        int[] dp = new int[target + 1];
        //第0位置可以组成 0或nums[0]
        dp[0] = 1;
        dp[nums[0]] += 1;
        for (int i = 1; i < nums.length; i++) {
            //对j逆序更新，不会影响结果。正序会影响结果,变成完全背包
            for (int j = target; j >= nums[i]; j--) {
                //dp[j] = 当前num不要 + 当前num要 = dp[j] + dp[j - nums[i]]
                dp[j] = dp[j] + dp[j - nums[i]];
            }
        }
        return dp[target];
    }

    /**
     * 方式3：DP，转01背包
     * <p>
     * dp[i][j]表示：当前位置i形成和为j的种数
     * <p>
     * 状态转移方程 dp[i][j] =  dp[i][j+nums[i]] + dp[i][j-nums[i]]
     * <p>
     * 考虑到负数情况，并且题目给的最大和为1000，所以改为
     * <p>
     * dp[i][j+1000] = dp[i][j+nums[i]+1000]+dp[i][j-nums[i]+1000]
     */
    private static final int MAX_SUM = 1000;

    private static int dp1(int[] nums, int S) {
        int number = nums.length - 1;
        //和范围是 -1000,1000，总共2001个
        int[][] dp = new int[number + 1][2 * MAX_SUM + 1];
        //初始化0号位置的元素
        dp[0][MAX_SUM + nums[0]] = 1;
        //注意要考虑nums[0]= 0，所以这里是 +=
        dp[0][MAX_SUM - nums[0]] += 1;
        //从1号元素开始dp
        for (int i = 1; i <= number; i++) {
            for (int j = 0; j <= 2 * MAX_SUM; j++) {
//                dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]];
                if (j - nums[i] >= 0) {
                    dp[i][j] += dp[i - 1][j - nums[i]];
                }
                if (j + nums[i] <= 2 * MAX_SUM) {
                    dp[i][j] += dp[i - 1][j + nums[i]];
                }
            }
        }
        return dp[number][S + MAX_SUM];
    }

    /**
     * 方式3的空间优化。
     * <p>
     * 由于转移方程为 dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]];
     * <p>
     * 所以无法优化到只用一个一维数组，因为无论正序还是逆序遍历，都会被影响。
     * <p>
     * 可以优化到用两个一维数组。
     */
    private static int dp1_1(int[] nums, int S) {
        int number = nums.length - 1;
        //和范围是 -1000,1000，总共2001个
        int[][] dp = new int[2][2 * MAX_SUM + 1];
        //初始化0号位置的元素
        dp[0][MAX_SUM + nums[0]] = 1;
        //注意要考虑nums[0]= 0，所以这里是 +=
        dp[0][MAX_SUM - nums[0]] += 1;
        int row = 0;
        //从1号元素开始dp
        for (int i = 1; i <= number; i++) {
            //row交替0,1
            row = 1 - row;
            for (int j = 0; j <= 2 * MAX_SUM; j++) {
//                dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]];
                //注意要清空当位置，不然会被上上次留下的影响到。
                dp[row][j] = 0;
                if (j - nums[i] >= 0) {
                    dp[row][j] += dp[1 - row][j - nums[i]];
                }
                if (j + nums[i] <= 2 * MAX_SUM) {
                    dp[row][j] += dp[1 - row][j + nums[i]];
                }
            }
        }
        return dp[row][S + MAX_SUM];
    }

    //方式2：带有记忆性回溯，可变参数为(index,curSum)表示当前位置index形成和为curSum的种数

    /**
     * 方式1：暴力递归
     */
    private static void process1(int[] nums, int curSum, int index) {
        if (index == nums.length) {
            if (curSum == 0) res++;
            return;
        }
        //当前位置或正或负
        process1(nums, curSum - nums[index], index + 1);
        process1(nums, curSum + nums[index], index + 1);
    }
}
